package com.study.lilhan.niuke.demo.linkPointer;

import com.study.lilhan.niuke.demo.bean.ListNode;

import java.util.Stack;

/**
 * @Author: lihan
 * @Date : 2022/1/4- 01
 * @DESCRIPTION: 判断一个链表否是回文结构
 *
 * 关键是，如何把开头和结尾的依次配对
 * 先分成两半，后面的逆序
 * @version: 1.0
 */
public class My96 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode();
        node1.val = 1;
        ListNode node2 = new ListNode(2,node1);
        ListNode node3 = new ListNode(2,node2);
        ListNode node4 = new ListNode(1,node3);
        boolean result = isPail(node4);
        System.out.println(result);

    }

    public static  boolean isPail (ListNode head) {
        if(head == null){
            return false;
        }
        if (head.next == null){
            return  true;
        }
        boolean flag = true;
        ListNode slowPointer = head;
        ListNode fastPoiner = head;
//标志这个链表是否含有双数

        /**
         * 不需要判断这个链表是奇数个，还是偶数个，把中间节点的左边逆序，然后比较
         **/
        boolean isDouble = true;
        ListNode lastHalfStart ;
        while (true){
            if(fastPoiner.next == null){//基数个，一步不能走
                isDouble = false;
                break;
            }
            if(fastPoiner.next.next == null){//偶数个，只能走一步
                break;
            }
            fastPoiner = fastPoiner.next.next;
//最后一步，基数个不走，偶数个走
            if(fastPoiner.next != null && fastPoiner.next.next ==null ){//快指针下回不能走了，是最后一步
                slowPointer = slowPointer.next;
            }


        }
        if(isDouble){
            lastHalfStart = slowPointer.next;
            slowPointer.next = null;

        }else{
            lastHalfStart = slowPointer.next.next;
            ListNode center =  slowPointer.next;
            center.next = null;
            slowPointer.next = null;


        }
        lastHalfStart = ReverseList(lastHalfStart);
        flag = isEqual(head,lastHalfStart);
       return flag;
    }

    public static  ListNode ReverseList(ListNode head) {
        if(head == null){
            return  null;
        }
        ListNode newHead = head;
        ListNode curNode = head.next;
        newHead.next = null;
        while (curNode != null){
            ListNode nextNode = curNode.next;
            curNode.next = newHead;
            newHead = curNode;
            curNode = nextNode;
        }

        return  newHead;
    }

    public static  boolean isEqual(ListNode firstPointer, ListNode secondPoiner){
        boolean flag = true;
        while (firstPointer != null){
            if(firstPointer.val != secondPoiner.val){
                flag = false;
                return flag;
            }
            firstPointer = firstPointer.next;
            secondPoiner = secondPoiner.next;
        }
        return flag;
    }
}
